package com.leetcode.partition4;

import java.util.Set;
import java.util.TreeSet;

/**
 * 并查集参考：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/solution/shi-jian-fu-za-du-cha-ru-o1cha-xun-wei-o-zziu/
 * @author `RKC`
 * @date 2021/10/9 11:18
 */
public class LC352将数据流变为多个不相交区域 {

    private static class SummaryRanges {
        private static final int BOUND = 10001;
        private int[] ancestor = new int[BOUND];
        //维护一个右边界
        private int[] rightBound = new int[BOUND];
        private boolean[] exists = new boolean[BOUND];
        //set维护已有的分段数量
        private Set<Integer> set = new TreeSet<>();

        public SummaryRanges() {
            for (int i = 0; i < BOUND; i++) {
                ancestor[i] = i;
                rightBound[i] = i;
            }
        }

        public void addNum(int val) {
            if (exists[val]) return;
            exists[val] = true;
            if (val > 0 && exists[val - 1]) union(val - 1, val);
            if (val < BOUND - 1 && exists[val + 1]) union(val, val + 1);
            if (find(val) == val) set.add(val);
        }

        public int[][] getIntervals() {
            int[][] ans = new int[set.size()][2];
            int i = 0;
            for (Integer s : set) {
                if (find(s) != s) continue;
                ans[i][0] = s;
                ans[i++][1] = rightBound[s];
            }
            return ans;
        }

        private int find(int x) {
            if (x != ancestor[x]) ancestor[x] = find(ancestor[x]);
            return ancestor[x];
        }

        private void union(int x, int y) {
            int ancestorX = find(x), ancestorY = find(y);
            if (ancestorX < ancestorY) {
                ancestor[ancestorY] = ancestorX;
                rightBound[ancestorX] = rightBound[ancestorY];
                set.remove(ancestorY);
            }
        }
    }
}
